package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-31 12:38
 */
public class Test31 {
    public static void main(String[] args) {

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //1 <= k <= n <= 5000
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }
        if (head == null || head.next == null) {
            return head;
        }
        ListNode resHead = null;
        ListNode p = head;
        // 节点往后移动 k 个
        for (int i = 0; i < k; i++) {
            p = p.next;
        }
        ListNode[] listNodes = reverseList(head, k);
        resHead = listNodes[0];
        ListNode lastNode = listNodes[1];
        while (true) {
            if (check(p, k)) {
                ListNode temp = p;
                for (int i = 0; i < k; i++) {
                    p = p.next;
                }
                listNodes = reverseList(temp, k);
                lastNode.next = listNodes[0];
                lastNode = listNodes[1];
            } else {
                lastNode.next = p;
                break;
            }

        }
        return resHead;
    }

    /**
     * 反转k个节点
     *
     * @param head
     * @param k
     * @return 头节点和尾节点
     */
    public ListNode[] reverseList(ListNode head, int k) {
        ListNode resHead = head;
        ListNode p = resHead.next;
        resHead.next = null;
        k--;
        while (p != null) {
            ListNode tempP = p;
            p = p.next;
            k--;
            tempP.next = resHead;
            resHead = tempP;
            if (k == 0) {
//                head.next = p;
                break;
            }
        }
        ListNode[] res = new ListNode[2];
        res[0] = resHead;
        res[1] = head;
        return res;
    }

    /**
     * @param head
     * @param k
     * @return false 不用反转 true 需要反转
     */
    private boolean check(ListNode head, int k) {
        int temp = k;
        ListNode p = head;
        while (p != null) {
            p = p.next;
            temp--;
        }
        return temp <= 0;// temp <= 0  节点个数 >= k 可以反转
    }

}
